// 插入排序 时间复杂度n2
function insertionSort(arr) {
  let len = arr.length
  let preIndex, current
  for (let i = 1; i < len; i++) { // 假设第一个数已经排序
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}
// 只是改变下当前值的表示
function insertionSort2(arr) {
  let len = arr.length, current
  for (let i = 1; i < len; i++) { // 假设第一个数已经排序
    let j = i
    current = arr[i]
    while (j - 1 >= 0 && current < arr[j - 1]) {
      arr[j] = arr[j - 1]
      j--
    }
    arr[j] = current
  }
  return arr
}

const arr = [5, 4, 3, 2, 1]
console.log(insertionSort(arr))
console.log(insertionSort2(arr))